package com.xyzboom.compiler.fa

import com.fasterxml.jackson.databind.JavaType
import com.fasterxml.jackson.databind.annotation.JsonDeserialize
import com.fasterxml.jackson.databind.annotation.JsonSerialize
import com.fasterxml.jackson.databind.util.StdConverter
import com.fasterxml.jackson.module.kotlin.jsonMapper
import com.fasterxml.jackson.module.kotlin.kotlinModule
import com.xyzboom.compiler.NoArg
import com.xyzboom.compiler.fa.toDFA
import com.xyzboom.compiler.excepitons.fa.LackOfCharException
import com.xyzboom.compiler.excepitons.fa.UnexpectedCharException
import com.xyzboom.compiler.fa.DFA
import com.xyzboom.compiler.fa.regex.parseRegex
import com.xyzboom.compiler.util.show
import com.xyzboom.compiler.util.toGraphViz
import com.xyzboom.compiler.util.generateRandom
import mu.KotlinLogging
import org.junit.jupiter.api.Assertions
import org.junit.jupiter.api.Assertions.*
import org.junit.jupiter.api.Test

private val logger = KotlinLogging.logger { }

internal class NfaAndDfaTest {

    //<editor-fold desc="testReg * + ? | () []">
    @Test
    fun testRegex1() {
        val nfa = parseRegex("(ab)")
        val dfa = nfa.toDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("ab".toList()))
        assertFalse(dfa.acceptable("abc".toList()))
        assertFalse(dfa.acceptable("ba".toList()))
        assertFalse(dfa.acceptable("baa".toList()))
    }

    @Test
    fun testReg2() {
        val nfa = parseRegex("(abcde)")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("abcde".toList()))
        assertFalse(dfa.acceptable("acbde".toList()))
    }

    @Test
    fun testReg3() {
        val nfa = parseRegex("a|b")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
    }

    @Test
    fun testReg4() {
        val nfa = parseRegex("a*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("aaaaaaaa".toList()))
    }

    @Test
    fun testReg5() {
        val nfa = parseRegex("(a|b)*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("aaaaaa".toList()))
        assertTrue(dfa.acceptable("abababab".toList()))
        assertTrue(dfa.acceptable("aaabbaabbaabbbb".toList()))
        assertTrue(dfa.acceptable("ababbabbbabbbbabbbbbabbbbb".toList()))
        assertTrue(dfa.acceptable("babaabaaabaaaabaaaaabaaaaa".toList()))
        assertFalse(dfa.acceptable("c".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaac".toList()))
    }

    @Test
    fun testReg6() {
        val nfa = parseRegex("(a|b|c)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("c".toList()))
    }

    @Test
    fun testReg7() {
        val nfa = parseRegex("((a|b)*|v)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("v".toList()))
        assertTrue(dfa.acceptable("aaaaaa".toList()))
        assertTrue(dfa.acceptable("abababab".toList()))
        assertTrue(dfa.acceptable("aaabbaabbaabbbb".toList()))
        assertTrue(dfa.acceptable("ababbabbbabbbbabbbbbabbbbb".toList()))
        assertTrue(dfa.acceptable("babaabaaabaaaabaaaaabaaaaa".toList()))
        assertFalse(dfa.acceptable("c".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaac".toList()))
        assertFalse(dfa.acceptable("vv".toList()))
        assertFalse(dfa.acceptable("vaaabbc".toList()))
    }

    @Test
    fun testReg8() {
        val nfa = parseRegex("((a|b|c)*|v)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("v".toList()))
        assertTrue(dfa.acceptable("cccc".toList()))
        assertTrue(dfa.acceptable("aaacccaaa".toList()))
        assertTrue(dfa.acceptable("ababccabab".toList()))
        assertTrue(dfa.acceptable("aaabbaccabbaabbbb".toList()))
        assertTrue(dfa.acceptable("ababbabbccbabbbbabbbbbabbbbb".toList()))
        assertTrue(dfa.acceptable("babaabaaabccccaaaabaaaaabaaaaa".toList()))
        assertFalse(dfa.acceptable("cv".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaap".toList()))
        assertFalse(dfa.acceptable("vv".toList()))
        assertFalse(dfa.acceptable("vaaabbc".toList()))
    }

    @Test
    fun testReg9() {
        val nfa = parseRegex("((a|b)*|(v|m))")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("v".toList()))
        assertTrue(dfa.acceptable("m".toList()))
        assertTrue(dfa.acceptable("aaaaaa".toList()))
        assertTrue(dfa.acceptable("abababab".toList()))
        assertTrue(dfa.acceptable("aaabbaabbaabbbb".toList()))
        assertTrue(dfa.acceptable("ababbabbbabbbbabbbbbabbbbb".toList()))
        assertTrue(dfa.acceptable("babaabaaabaaaabaaaaabaaaaa".toList()))
        assertFalse(dfa.acceptable("c".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaac".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaav".toList()))
        assertFalse(dfa.acceptable("babaabaaabaaaabaaaaabaaaaam".toList()))
    }

    @Test
    fun testReg10() {
        val nfa = parseRegex("a|b*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("bb".toList()))
        assertTrue(dfa.acceptable("bbbbb".toList()))
        assertTrue(dfa.acceptable("bbbbbbb".toList()))
        assertTrue(dfa.acceptable("bbbbbbbbbbb".toList()))
        assertFalse(dfa.acceptable("ab".toList()))
    }

    @Test
    fun testReg11() {
        val nfa = parseRegex("a|b*(c|d)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("bc".toList()))
        assertTrue(dfa.acceptable("bd".toList()))
        assertTrue(dfa.acceptable("bbc".toList()))
        assertTrue(dfa.acceptable("bbd".toList()))
        assertTrue(dfa.acceptable("bbbbbc".toList()))
        assertTrue(dfa.acceptable("bbbbbd".toList()))
        assertTrue(dfa.acceptable("bbbbbbbc".toList()))
        assertTrue(dfa.acceptable("bbbbbbbd".toList()))
        assertTrue(dfa.acceptable("bbbbbbbbbbbd".toList()))
        assertFalse(dfa.acceptable("ab".toList()))
    }

    @Test
    fun testReg12() {
        val nfa = parseRegex("a|b*(ui*|(y*ua*)i*)a")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("a".toList()))
        assertTrue(dfa.acceptable("ua".toList()))
        assertTrue(dfa.acceptable("uiiia".toList()))
        assertTrue(dfa.acceptable("yyyyuaaiiia".toList()))
        assertTrue(dfa.acceptable("bua".toList()))
        assertTrue(dfa.acceptable("buiiia".toList()))
        assertTrue(dfa.acceptable("byyyyuaaiiia".toList()))
        assertTrue(dfa.acceptable("bbbua".toList()))
        assertTrue(dfa.acceptable("bbbbuiiia".toList()))
        assertTrue(dfa.acceptable("bbbbbyyyyuaaiiia".toList()))
        assertTrue(dfa.acceptable("bbbbbyyyyuiiia".toList()))
        assertFalse(dfa.acceptable("bbbbbyyyyuiuiiia".toList()))
    }

    @Test
    fun testReg13() {
        assertThrowsExactly(LackOfCharException::class.java) {
            parseRegex("(a|b|c*")
        }
        assertThrowsExactly(UnexpectedCharException::class.java) {
            parseRegex("(a|b|c*))")
        }
        assertThrowsExactly(UnexpectedCharException::class.java) {
            parseRegex("a|c|d((a|b|c*)))")
        }
        assertThrowsExactly(LackOfCharException::class.java) {
            parseRegex("(a|c|d(a|b|c*)")
        }
    }

    @Test
    fun testReg14() {
        val nfa = parseRegex("\\\\*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("\\".toList()))
        assertTrue(dfa.acceptable("\\\\".toList()))
    }

    @Test
    fun testReg15() {
        val nfa = parseRegex("\\\\\\*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        assertTrue(dfa.acceptable("\\*".toList()))
        assertFalse(dfa.acceptable("\\\\".toList()))
    }

    @Test
    fun testReg16() {
        val nfa = parseRegex("(a*b|a*c)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("c".toList()))
        assertTrue(dfa.acceptable("aaaaaab".toList()))
        assertTrue(dfa.acceptable("ab".toList()))
        assertTrue(dfa.acceptable("aac".toList()))
        assertTrue(dfa.acceptable("aaaaaaac".toList()))
        assertFalse(dfa.acceptable("".toList()))
    }

    @Test
    fun testReg17() {
        val nfa = parseRegex("(a+b|a+c)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("b".toList()))
        assertFalse(dfa.acceptable("c".toList()))
        assertTrue(dfa.acceptable("aaaaaab".toList()))
        assertTrue(dfa.acceptable("ab".toList()))
        assertTrue(dfa.acceptable("aac".toList()))
        assertTrue(dfa.acceptable("aaaaaaac".toList()))
        assertFalse(dfa.acceptable("".toList()))
    }

    @Test
    fun testReg18() {
        val nfa = parseRegex("((am)?b|(va)?c)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        assertFalse(dfa.acceptable("amc".toList()))
        assertFalse(dfa.acceptable("vab".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("amb".toList()))
        assertTrue(dfa.acceptable("c".toList()))
        assertTrue(dfa.acceptable("vac".toList()))
        assertFalse(dfa.acceptable("amamb".toList()))
        assertFalse(dfa.acceptable("vavac".toList()))
    }

    @Test
    fun testReg19() {
        val nfa = parseRegex("((am)+b|(va)+c)")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        assertFalse(dfa.acceptable("amc".toList()))
        assertFalse(dfa.acceptable("vab".toList()))
        assertFalse(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("amb".toList()))
        assertFalse(dfa.acceptable("c".toList()))
        assertTrue(dfa.acceptable("vac".toList()))
        assertTrue(dfa.acceptable("amamb".toList()))
        assertTrue(dfa.acceptable("amamamamb".toList()))
        assertFalse(dfa.acceptable("amamamab".toList()))
        assertFalse(dfa.acceptable("amammamb".toList()))
        assertTrue(dfa.acceptable("vavac".toList()))
        assertTrue(dfa.acceptable("vavavavac".toList()))
        assertFalse(dfa.acceptable("vavavvac".toList()))
        assertFalse(dfa.acceptable("vavavavc".toList()))
    }

    @Test
    fun testReg20() {
        val nfa = parseRegex("[a-zA-Z]")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        for (c in 'a'..'z') {
            assertTrue(dfa.acceptable(arrayListOf(c)))
        }
        for (c in 'A'..'Z') {
            assertTrue(dfa.acceptable(arrayListOf(c)))
        }
        assertFalse(dfa.acceptable("ab".toList()))
        assertFalse(dfa.acceptable("cv".toList()))
    }

    @Test
    fun testReg21() {
        val nfa = parseRegex("[a-zA-Z]*")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertTrue(dfa.acceptable("".toList()))
        for (i in 0..50) {
            val sb = StringBuilder()
            for (j in 0..(10..100).random()) {
                if ((0..1).random() == 0)
                    sb.append(('a'..'z').random())
                else
                    sb.append(('A'..'Z').random())
            }
            assertTrue(dfa.acceptable(sb.toList()))
        }
    }

    @Test
    fun testReg22() {
        val nfa = parseRegex("[a-zA-Z]+")
        val dfa = nfa.toDFA().intStateDFA().getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        for (i in 0..50) {
            val sb = StringBuilder()
            for (j in 0..(10..100).random()) {
                if ((0..1).random() == 0)
                    sb.append(('a'..'z').random())
                else
                    sb.append(('A'..'Z').random())
            }
            assertTrue(dfa.acceptable(sb.toList()))
        }
    }

    @Test
    fun testReg23() {
        val nfa = parseRegex("[a-z\\-A-Z]+")
        val dfa = nfa.toDFA().intStateDFA()//.getSimplest().intStateDFA()
        assertFalse(dfa.acceptable("".toList()))
        for (i in 0..50) {
            val sb = StringBuilder()
            for (j in 0..(10..100).random()) {
                when ((0..2).random()) {
                    0 -> sb.append(('a'..'z').random())
                    1 -> sb.append(('A'..'Z').random())
                    2 -> sb.append('-')
                }
            }
            assertTrue(dfa.acceptable(sb.toList()))
        }
    }

    //</editor-fold>
    //<editor-fold desc="testReg .">
    @Test
    fun testRegex24() {
        val nfa = parseRegex("(.b)")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("ab".toList()))
        assertTrue(dfa.acceptable(" b".toList()))
        assertTrue(dfa.acceptable("1b".toList()))
        assertTrue(dfa.acceptable("/b".toList()))
        assertFalse(dfa.acceptable("\nb".toList()))
        assertFalse(dfa.acceptable("abc".toList()))
        assertFalse(dfa.acceptable("ba".toList()))
        assertFalse(dfa.acceptable("baa".toList()))
    }

    @Test
    fun testRegex25() {
        val nfa = parseRegex("\".*\"")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("\"\"".toList()))
        val sb = StringBuilder()
        for (c in Char.MIN_VALUE..Char.MAX_VALUE) {
            if (c != '\n' && c != '\r')
                sb.append(c)
        }
        for (i in 0..150) {
            assertTrue(
                dfa.acceptable(
                    "\"${sb.toString().generateRandom(1 shl 10)}\""
                        .toList()
                )
            )
        }
    }

    @Test
    fun testRegex26() {
        val nfa = parseRegex("\\n")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("\n".toList()))
        assertFalse(dfa.acceptable("a".toList()))
        assertFalse(dfa.acceptable("b".toList()))
    }

    @Test
    fun testRegex27() {
        val nfa = parseRegex("(.*b|a)")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        val sb = StringBuilder()
        for (c in Char.MIN_VALUE..Char.MAX_VALUE) {
            if (c != '\n' && c != '\r')
                sb.append(c)
        }
        for (i in 0..150) {
            assertTrue(
                dfa.acceptable(
                    "${sb.toString().generateRandom(1 shl 10)}b"
                        .toList()
                )
            )
        }
    }

    @Test
    fun testRegex28() {
        val nfa = parseRegex("(\\s*b|a)")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("a".toList()))
        val sb = StringBuilder()
        for (c in arrayListOf(' ', '\n', '\r', '\u000c', '\u000b', '\t')) {
            sb.append(c)
        }
        for (i in 0..150) {
            assertTrue(
                dfa.acceptable(
                    "${sb.toString().generateRandom(1 shl 10)}b"
                        .toList()
                )
            )
        }
    }

    @Test
    fun testRegex29() {
        val nfa = parseRegex("[^ad][^cd]b*")
        val dfa = nfa.toDFA()
        assertTrue(dfa.acceptable("ca".toList()))
        assertTrue(dfa.acceptable("ctbbb".toList()))
        assertTrue(dfa.acceptable("mmbbb".toList()))
        assertFalse(dfa.acceptable("abbb".toList()))
        assertFalse(dfa.acceptable("dbbb".toList()))
        assertFalse(dfa.acceptable("ccbbb".toList()))
        assertFalse(dfa.acceptable("gdbbb".toList()))
        assertFalse(dfa.acceptable("fdbbb".toList()))
    }

    @Test
    fun testRegex30() {
        val nfa = parseRegex("\"([^\"]*|\\\\\")\"")
        val dfa = nfa.toDFA()
//        nfa.toGraphViz().show()
        assertTrue(dfa.acceptable("\"\"".toList()))
        assertTrue(dfa.acceptable("\"ad\"".toList()))
        assertFalse(dfa.acceptable("\"".toList()))
        assertFalse(dfa.acceptable("\"%s\", \"123\"".toList()))
    }

    @Test
    fun testRegex31() {
        val nfa = parseRegex("\\*\\*\\*(.|\n|\r)*\\*\\*\\*")
        val dfa = nfa.toDFA()
        dfa.getSimplest().toGraphViz().show()
        assertTrue(dfa.acceptable("******".toList()))
        assertTrue(dfa.acceptable("***1***".toList()))
        assertTrue(dfa.acceptable("***133***".toList()))
        assertTrue(dfa.acceptable("*********".toList()))
        assertTrue(dfa.acceptable("***\n***".toList()))
    }

    @Test
    fun testNoGreedy0() {
        val nfa = parseRegex("a*")
        val dfa = nfa.toDFA()
//        dfa.getSimplest().toGraphViz().show()
        assertEquals(0, dfa.acceptFrom(0, "aaaaa".toList(), false))
    }

    @Test
    fun testNoGreedy1() {
        val nfa = parseRegex("/\\*.*\\*/")
        val dfa = nfa.toDFA()
//        dfa.getSimplest().toGraphViz().show()
        assertEquals(4, dfa.acceptFrom(0, "/**/*/".toList(), false))
        val str = "0/**/"
        assertEquals(str.length, dfa.acceptFrom(1, str.toList(), false))
    }

    @Test
    fun testNoGreedy2() {
        val nfa = parseRegex("\"((\\\\\")|[^\"\\\\])*\"")
        val dfa = nfa.toDFA()
//        dfa.getSimplest().toGraphViz().show()
        assertTrue(dfa.acceptable("\"\\\"\"".toList()))
        assertTrue(dfa.acceptable("\"hello world!\\\", %s %f\"".toList()))
        val str0 = "\"\\\"\", \"1\""
        assertFalse(dfa.acceptable(str0.toList()))
        assertEquals(4, dfa.acceptFrom(0, str0.toList(), false))
        val str1 = "\"hello world!\\\", %s %f\", \"123\""
        assertEquals(23, dfa.acceptFrom(0, str1.toList(), false))
//        val str = "0/**/"
//        assertEquals(str.length, dfa.acceptFrom(1, str.toList(), false))
    }

    //</editor-fold>
    @Test
    fun testdfaSimplest1() {
        val nfa = parseRegex("a*c|a*b")
        val dfa = nfa.toDFA().intStateDFA()
        assertTrue(dfa.acceptable("aaaaac".toList()))
        assertTrue(dfa.acceptable("aaaaab".toList()))
        assertTrue(dfa.acceptable("b".toList()))
        assertTrue(dfa.acceptable("c".toList()))
        assertFalse(dfa.acceptable("cb".toList()))
        assertFalse(dfa.acceptable("caaaa".toList()))
        assertFalse(dfa.acceptable("aaaa".toList()))
        assertFalse(dfa.acceptable("a".toList()))
    }


    @Test
    fun testDFASerialize() {
        val jsonMapper = jsonMapper()
        val nfa = parseRegex("a*c|a*b")
        val dfa = nfa.toDFA().intStateDFA()
        val json = jsonMapper.writeValueAsString(dfa)
        logger.trace { json }
        val dfaClass = jsonMapper.typeFactory.constructParametricType(
            DFA::class.java, Int::class.java, Char::class.java
        )
        val dfaDeserialized = jsonMapper.readerFor(dfaClass)
            .readValue<DFA<Int, Char>>(json)
        dfaDeserialized.toGraphViz().show()
    }

}